# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
root=TreeNode(1)
root.left=TreeNode(2)
root.left.left=TreeNode(4)
root.left.right=TreeNode(5)
root.right=TreeNode(3)
root.right.left=TreeNode(6)

#深度优先遍历，用来计算树的深度
def dfs(root,height,curHeight):
    if root.left==None and root.right==None:
        if curHeight>=height[0]:
            height[0]=curHeight
            return 1
        else:
            return 0
    if root.left!=None and root.right!=None:
        leftCount=dfs(root.left,height,curHeight+1)
        rightCount=dfs(root.right,height,curHeight+1)
        return leftCount+rightCount
    if root.left!=None and root.right==None:
        leftCount=dfs(root.left,height,curHeight+1)
        return leftCount
    if root.left==None and root.right!=None:
        rightCount=dfs(root.right,height,curHeight+1)
        return rightCount

def countNodes(root):
    #设置一个
    height=[0]
    sonNodeCount=dfs(root,height,0)
    print(sonNodeCount)
    print(height)
    return sonNodeCount+pow(2,height[0])-1
print(countNodes(root))